Пусть p>2 простое число. Эллиптическая кривая E задается уравнением
y 2 = x3+ax+b (mod p ) (*)
над конечным простым полем. Предположим, что группа E(Fp)
содержит подгруппу простого порядка q, которая порождается точкой
G из группы E(Fq).
Перейдем к рассмотрению протокола электронной цифровой подписи. Известными считаются
эллиптическая кривая (*), в том числе простое число p и
точка G из группы E(Fp). Секретным ключем является s (mod q), а открытым -
точка W=sG из E(Fp).
Пусть вычет m (mod q) - хэш-значение подписываемого сообщения. Чтобы получить
подпись для m, необходимо выполнить следующие шаги.
Выбирать случайный вычет u(mod q) ( и хранить его в секрете),
где 0<u<q. Вычислить точку
V = uG =(xV,yV),
где представитель класса
вычетов xV выбирается из фиксированного интервала 0 < xV < p.
Вычислить c=xV (mod q) . Если c=0(mod q) , то перейти к шагу 1.
В противном случае вычислить
d=u-1 (m+sc)(mod q).
Если d=0 (mod q) , то перейти к шагу 1. В противном случае пара чисел (c,d), где 0<c,d<q
есть подпись для m.
Чтобы проверить подпись под сообщением m (хэш - значением сообщения) необходимо
выполнить следующие шаги.
Вычислить h=d-1 (mod q) и вычеты
h1 =hm (mod q), h2 = hc (mod q).
Вычисляет точку P=h1G+h2W =(xP,yP), 0 <= xP <p.
Если c=xP (mod q) , то подпись принимается, в противном случае - отвергается.
Несложно заметить, что эта схема, как и новый ГОСТ является переложением стандарта DSA на эллиптические кривые.
В [7] высказано предположение о том, что этот переход связан с большими успехами специальных
служб России и США в решении задач дискретного логарифмирования.
Слабость цифровой подписи ECDSA
Автор работы [5] считает, что новый стандарт небезопасен, так как позволяет имитировать
подмену подписи. По его мнению, недостаток ECDSA в том, что этот стандарт позволяет рядовому пользователю
выбрать свои секретный и открытый ключи так, что подписи для двух известных заранее сообщений совпадут. А это
открывает простор для различных махинаций с использованием ЭЦП.
Возможность имитации подделки основывается на том, что x-координаты противоположных точек эллиптических кривых
совпадают. Если qG=0, то (q-1)G = -G, следовательно справедливы равенства:
c1 = xG = c2 = x(q-1)G = c,
где 0 - бесконечно удаленная точка эллиптической кривой (нейтральный элемент относительно операции +).
Положим случайные вычеты q1 и q2 равными 1 и (q-1). Отметим также, что
(q-1)-1 = (q-1) (mod q).
Подберем две одинаковые подписи для сообщений m1 и m2. Уравнения подписи имеют вид:
d1 = u1-1 (m1 + sc) (mod q) = (m1 + sc) (mod q),
d2 = u2-1 (m2 + sc) (mod q) = (q-1)(m2 + sc) (mod q).
Нам нужно, чтобы выполнялось равенство d1 = d2. Получим уравнение:
m1+sc = (q-1)(m2 +sc) (mod q).
Отсюда легко находится s:
2cs = (q-1)(m1 + m2) (mod q).
Так как q - простое число, то это уравнение однозначно разрешимо относительно s.
Таким образом, мы получили две одинаковые подписи для двух заранее выбранных сообщений.
